import java.util.PriorityQueue;

/**
 * Created With IntelliJ IDEA
 * Description:牛客网：BM48 数据流中的中位数
 * <a href="https://www.nowcoder.com/practice/9be0172896bd43948f8a32fb954e1be1?tpId=295&tqId=23457&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj">...</a>
 * User: DELL
 * Data: 2023-03-22
 * Time: 22:40
 */
import java.util.*;

/**
 * 总体思路就是维护一个大根堆和一个小根堆，大根堆中存储数据流中较小的那一半数字，
 * 小根堆中存储数据流中较大的那一半的数字，然后约定大根堆中数字个数不小于小根堆
 * 中数字的个数，且大根堆中数字的个数最多必小根堆中数字的个数多一个，这样子做是
 * 为了方便我们得到中位数，即两个堆中数字个数相等的时候返回两个堆堆顶元素的平均
 * 值，而不相等的时候，返回大根堆的堆顶元素即可，同时在每次插入的时候，调整两个
 * 堆达到上述状态即可。
 *
 * 另一个方法是利用插入排序，较为简单，这里省略。
 */
public class Solution {
    //利用大根堆存储数据流中的小数字
    private PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1, o2) -> o2-o1);
    //利用小根堆存储数据流中的大数字
    private PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    public void Insert(Integer num) {
        if (minHeap.isEmpty() && maxHeap.isEmpty()) {
            maxHeap.add(num);
        } else {
            if (maxHeap.peek() < num) {
                minHeap.add(num);
            } else {
                maxHeap.add(num);
            }
            //调平衡
            adjustBalance();
        }
    }
    //这个函数是因为我们每一次插入均调用这个函数调平衡，因此如果不平衡，我们最多只需要调整一步就可以了
    private void adjustBalance() {
        if (maxHeap.size() > minHeap.size() + 1) {
            minHeap.add(maxHeap.poll());
        } else if (maxHeap.size() < minHeap.size()) {
            maxHeap.add(minHeap.poll());
        }
    }
    public Double GetMedian() {
        if (maxHeap.size() == minHeap.size()) {
            return (double)(minHeap.peek()+maxHeap.peek())/2.0;
        } else {
            return (double)maxHeap.peek();
        }
    }
}